package com.ly.algorithm.leetcode.backtracking;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Classname Problem90
 * @Description
 *
 *
 *  * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 *  *
 *  * 说明：解集不能包含重复的子集。
 *  *
 *  * 示例:
 *  *
 *  * 输入: [1,2,2]
 *  * 输出:
 *  * [
 *  *   [2],
 *  *   [1],
 *  *   [1,2,2],
 *  *   [2,2],
 *  *   [1,2],
 *  *   []
 *  * ]
 *
 *
 * @Date 2020/12/14 20:37
 * @Author 冷心影翼
 */
public class Problem90 {

	public static void main(String[] args) {
		Solution90 solution90 = new Solution90();
		List<List<Integer>> lists = solution90.subsetsWithDup(new int[]{4,4,4,1,4});
		System.out.println(lists);
	}


}

class Solution90 {
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		List<List<Integer>> res = new ArrayList<>();
		Arrays.sort(nums);
		backtracking(0,nums,res,new ArrayList<>());
		return res;
	}

	private void backtracking(int index, int[] nums, List<List<Integer>> res, ArrayList<Integer> list) {

		res.add(new ArrayList<>(list));
		for(int i = index;i<nums.length;i++) {
			if(i > index && nums[i] == nums[i-1]) {
				continue;
			}
			list.add(nums[i]);
			backtracking(i+1,nums,res,list);
			list.remove(list.size()-1);
		}
	}
}